package com.fr.lintcode;

public class Q1721 {

    /**
     * @param S:
     *            the given string
     * @return: the minimum number of parentheses we must add
     */
    public int minAddToMakeValid(String S) {
        // Write your code here
        if (S == null || S.length() == 0) {
            return 0;
        }
        char[] cs = S.toCharArray();
        int count = 0;
        int left = 0;
        int right = 0;
        for (char c : cs) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                if (left > 0) {
                    left--;
                } else {
                    count++;
                }
            }
        }
        for (int i = cs.length - 1; i >= 0; i--) {
            char c = cs[i];
            if (c == ')') {
                right++;
            } else if (c == '(') {
                if (right > 0) {
                    right--;
                } else {
                    count++;
                }
            }
        }
        return count;
    }
}
